#include <iostream>
#include <vector>

using namespace std;

class NumMatrix {
public:
    NumMatrix(vector<vector<int> > matrix) {
        if(matrix.empty())
            return;
        this->matrix = matrix;
        int row = matrix.size();
        int col = matrix[0].size();
        for(int i = 0; i < row; ++i){
            for(int j = 0; j < col; ++j){
                if(i > 0)
                    this->matrix[i][j] += this->matrix[i-1][j];
                if(j > 0)
                    this->matrix[i][j] += this->matrix[i][j-1];
                if(i > 0 && j > 0)
                    this->matrix[i][j] -= this->matrix[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = this->matrix[row2][col2];
        if(row1 > 0)
            sum -= this->matrix[row1-1][col2];
        if(col1 > 0)
            sum -= this->matrix[row2][col1-1];
        if(row1 > 0 && col1 > 0)
            sum += this->matrix[row1-1][col1-1];
        return sum;
    }
private:
    vector<vector<int> > matrix;
};

int main(){
    int arr[][5] = {{3,0,1,4,2}, {5,6,3,2,1}, {1,2,0,1,5}, {4,1,0,1,7}, {1,0,3,0,5}};
    int len = sizeof(arr)/sizeof(int);
    int col = sizeof(arr[0])/sizeof(int);
    int row = len/col;
    vector<vector<int> > matrix;
    for(int i = 0; i < row; ++i){
        vector<int> vec(arr[i], arr[i]+col);
        matrix.push_back(vec);
/*         for(int j = 0; j < col; ++j){
            std::cout << arr[i][j] << " ";
        }
        std::cout << std::endl; */
    }
    NumMatrix* obj = new NumMatrix(matrix);
    int param_1 = obj->sumRegion(2,1,4,3);
    std::cout << param_1 << std::endl;
    return 0;
}